#include <iostream>

// 堆，树用数组存法
namespace {

void Swap(int array[], int a, int b);
void HeapifyMax(int array[], int n, int i);

class Heap {
public:
    Heap(int cap) {
        capacity = cap;
        count = 0,
        array = new int[cap + 1];
    }

    void Insert(int data) {
        if (count >= capacity) return;
        array[++count] = data;
        int i = count;
        // 和父节点比较，依次交换
        while (i/2 > 0 && array[i] > array[i/2]) {
            Swap(array, i, i/2);
            i = i/2;
        }
    }

    void RemoveTop() {
        if (count == 0) return;
        array[1] = array[count];
        --count;
        HeapifyMax(array, count, 1);
    }

    void Dump() {
        for (int i=1; i<=count; i++) {
            std::cout << array[i] << ",";
        }
        std::cout << std::endl;
    }

private:
    int capacity;
    int count;
    int *array;
};

// 打印数组
void DumpArray(int array[], int count) {
    for (int i=1; i<=count; i++) {
        std::cout << array[i] << ",";
    }
    std::cout << std::endl;
}

// 打印树形结构
// 根节点array[1]
void DumpTree(const std::string& prefix, int dir, int i, int array[], int count) {
    if (i > count) return;
    std::cout << prefix;
    std::string newPrefix = prefix;
    if (dir == 1) {
        std::cout << "├──";
        newPrefix += "│  ";
    }
    else if (dir == 2) {
        std::cout << "└──";
        newPrefix += "   ";
    }
    std::cout << array[i] << std::endl;
    DumpTree(newPrefix, 1, 2*i+1, array, count);
    DumpTree(newPrefix, 2, 2*i, array, count);
}

void DumpTree(int array[], int count) {
    DumpTree("", 0, 1, array, count);
}

void Swap(int array[], int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

// 大顶堆
// 节点 i，左子节点i*2，右子节点i*2+1，父节点i/2
void HeapifyMax(int array[], int n, int i) {
    while (true) {
        int maxPos = i;
        if (i*2 <= n && array[i] < array[i*2]) maxPos = i*2;
        if (i*2 + 1 <= n && array[maxPos] < array[i*2 + 1]) maxPos = i*2 + 1;
        if (maxPos == i) break;
        Swap(array, maxPos, i);
        i = maxPos;
    }
}

// 小顶堆
// 节点 i，左子节点i*2，右子节点i*2+1，父节点i/2
void HeapifyMin(int array[], int n, int i) {
    // while (true) {
    //     int maxPos = i;
    //     if (i*2 <= n && array[i] > array[i*2]) maxPos = i*2;
    //     if (i*2 + 1 <= n && array[maxPos] > array[i*2 + 1]) maxPos = i*2 + 1;
    //     if (maxPos == i) break;
    //     Swap(array, maxPos, i);
    //     i = maxPos;
    // }

    int j, temp;
    temp = array[i];
    for (j = 2 * i; j <= n; j *= 2) {
        // 比较左右子节点，取小的节点
        if (j < n && array[j] > array[j+1]) {
            j++;
        }
        // 如果当前节点更小则退出
        if (temp <= array[j]) {
            break;
        }
        // 否在交换节点数据，继续往下找更小的节点
        array[i] = array[j];
        i = j;
    }
    // 将当前节点换到最下面
    array[i] = temp;
}

void BuildHeap(int array[], int count) {
    // count/2为最后一个非叶子节点(节点编号从1开始)
    for (int i=count/2; i>=1; i--) {
        HeapifyMin(array, count, i);
    }
}

void HeapSort(int array[], int count) {
    BuildHeap(array, count);
    std::cout << "build heap " << std::endl;
    DumpTree(array, count);
    DumpArray(array, count);

    int k = count;
    while (k > 1) {
        // 根节点是最小值，调到最后，在剩余数据中重建最小堆，依次把最小值放到最后
        // 最后得出一个降序排列的数组
        Swap(array, 1, k);
        --k;
        HeapifyMin(array, k, 1);
    }
}

void Handle() {
    srand((unsigned)time(NULL));
    Heap *hp = new Heap(10);
    for (int i=0; i<10; i++) {
        hp->Insert(rand() % 50);
    }
    hp->Dump();
    hp->RemoveTop();
    hp->Dump();

    int array[11] = {0};
    int count = sizeof(array)/sizeof(int) - 1;
    for (int i=1; i<=count; i++) {
        array[i] = rand() % 100;
    }
    std::cout << "init array " << std::endl;
    DumpArray(array, count);
    HeapSort(array, count);
    std::cout << "sort heap " << std::endl;
    DumpTree(array, count);
    DumpArray(array, count);
}

}

void HandleHeap2() {
    Handle();
}